Năm 1986, Rice đảm nhiệm chức vụ phụ tá đặc biệt cho giám đốc Hội đồng Tham mưu Liên quân. Từ năm 1989 đến tháng 3 năm 1991 (giai đoạn chứng kiến bức tường Berlin sụp đổ và những ngày cuối cùng của Liên bang Xô viết), Rice phục vụ trong chính phủ George H. W. Bush với cương vị giám đốc, rồi tổng giám đốc Vụ Xô viết và Đông Âu thuộc Hội đồng An ninh Quốc gia, và là phụ tá đặc biệt cho tổng thống về các vấn đề an ninh quốc gia. Trong cương vị này, Rice giúp phát triển chính sách của ngoại trưởng James Baker theo hướng ủng hộ tiến trình thống nhất nước Đức. Rice tạo được ấn tượng tốt đối với tổng thống Bush đến nỗi có lần ông giới thiệu Rice với nhà lãnh đạo Xô viết Mikhail Sergeyevich Gorbachov như là một trong những người "bảo cho tôi biết mọi điều về Liên bang Xô viết".[18]

Năm 1989, khi phụ trách Vụ Xô viết và Đông Âu, Rice được phép báo cáo trực tiếp với Cố vấn An ninh Quốc gia Brent Scowcroft, người đã gặp Rice mười hai năm trước trong một bữa ăn tối tại Standford, và bị thuyết phục bởi kiến thức và sự tự tin của bà.[19] Khi được tổng thống tân cử George H. W. Bush mời trở về làm việc trong cương vị Cố vấn An ninh Quốc gia, tên của Rice có trong danh sách những người đầu tiên được Scowcroft chọn đến làm việc cho Hội đồng An ninh Quốc gia. Chẳng bao lâu sau đó, Rice thiết lập được mối quan hệ thân tình với gia đình Bush.

Năm 1990, bà trở thành cố vấn trưởng cho George H. W. Bush về Liên bang Xô viết.

Suốt trong chiến dịch tranh cử tổng thống năm 2000 của Georg W. Bush, Rice xin nghỉ phép một năm tại Đại học Stanford để dành thời gian làm việc với Bush trong cương vị cố vấn về chính sách ngoại giao. Rice đọc bài diễn văn then chốt tại Đại hội Toàn quốc Đảng Cộng hòa năm 2000, bà nhấn mạnh, "...Lực lượng vũ trang của Mỹ không phải là cảnh sát toàn cầu, mà là dịch vụ khẩn cấp 911 cho thế giới."[20][21]